package problem;

public class S_115 {
    /*给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
*/
    //1.暴力递归
    class Solution{
        private int res=0;
        public int numDistinct(String s, String t) {
            dfs(res,s,t,0,0);
            return res;
        }
        private void dfs(int res,String s,String t,int i,int j){
            if(j==t.length()){
                res++;
                return;
            }
            if(i==s.length()) return;
            dfs(res,s,t,i+1,j);
            if(s.charAt(i)==t.charAt(j)) dfs(res,s,t,i+1,j+1);
        }
    }

    //2.DP
    /*（一）状态

    f[i][j]表示s1的前i个字符的子序列中，包含多少个s2的前 j 个字符子串
    （二）转移方程

    如果s1的第 i 个字符和s2的第 j 个字符不同的话，
    意味着s1的第 i 个字符，必不参与组成子序列

    f[i][j] = f[i - 1][j]
    （例如 abc, ab) f[3][2] = f[2][2]
    如果s1的第 i 个字符和s2的第 j 个字符相同的话，
    意味着s1的第 i 个字符，可以参与组成子序列，也可不参与组成子序列

    f[i][j] = f[i - 1][j - 1] + f[i - 1][j]
    (例如 abcc, abc) f[4][3] = f[3][2] + f[3][3]
    （三）初始化

    s1的前 i 个字符和s2的前 0 个字符，意味着 s1 中子序列等于空串的个数都是 1
    f[i][0] = 1
    （四）结果

    f[m][n]
*/
    class Solution1{
        public int numDistinct(String s,String t){
            int m=s.length(),n=t.length();
            int[][] f=new int[m+1][n+1];
            for(int i=0;i<=m;i++) f[i][0]=1;
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    if(s.charAt(i-1)==t.charAt(j-1)) f[i][j]=f[i-1][j]+f[i-1][j-1];
                    else f[i][j]=f[i-1][j];
                }
            }
            return f[m][n];
        }
    }
}
